This invention relates to methods for intersymbol interference compensation in data communications and data storage systems with the objective of improving the reliability of data recovery.
Intersymbol interference (ISI) is found in many communications and recording systems. In order to reduce the frequency spectrum of a modulated signal, ISI may be introduced deliberately at the modulator. An example of modulation schemes that introduce ISI is Gaussian minimum shift keying (GMSK) described in the article: xe2x80x9cGMSK Modulation for Digital Mobile Radio Telephony,xe2x80x9d by K. Murota and K. Hirade, IEEE Transactions on Communications, vol. COM-29, pp. 1044-1050, July 1981. Filtering at the transmitter to control the signal spectrum can extend the basic modulation pulse beyond one signaling interval, thus introducing ISI. The communications medium is another potential source of ISI. In digital subscriber line (DSL) systems, which support high-rate data transmissions in addition to voice traffic, the severe line attenuation and delay variation with frequency of the telephone lines have been found to cause significant ISI in the received signal, as described in the book: Understanding Digital Subscriber Line Technology, by T. Starr et al., Prentice Hall, 1999, pp. 183-186. In mobile communications, ISI associated with multipath fading occurs when the direct-path signal combines with the reflected and delayed signals to form a composite signal at the receiver, as described in the book: Mobile Communications Engineering: Theory and Applications, Second Edition, by W. Lee, McGraw-Hill, 1998, pp. 442-445.
In reading data from a magnetic recording medium, a phenomenon referred to as bit crowding may occur if the bit packing density is high, as described in the book: Electronics Engineers"" Handbook, Fourth Edition, by D. Christiansen, McGraw-Hill, 1997, pp. 27.49-27.54. Bit crowding leads to ISI since a read head, which is a transducer configured to provide an output in response to a change in the polarity of the magnetization pattern, has a limited bandwidth. The transducer output is a pulse whose width is inversely proportional to the transducer""s bandwidth. When the bit packing density of the recording is sufficiently high, the response pulse will be become wide enough to have non-zero amplitude in the adjacent bit periods, resulting in ISI. There are precursor and postcursor ISI. Precursor ISI is caused by leading undershoots in the transducer response resulting from stray magnetic fields at the edges of the inductive read heads. Postcursor ISI is caused by trailing undershoots in the transducer response.
Modern high-end disk drive systems employ the partial response maximum likelihood (PRML) technology to achieve better performance. In this scheme a certain amount of ISI is deliberately introduced into the recorded signal in order to reduce constraints on the bandwidth of the electronic circuitry. During data recovery, the ISI is usually removed using a maximum likelihood detection scheme such as the Viterbi algorithm. A popular choice of partial response is the class IV partial response (PR4) characterized by the transfer function 1xe2x88x92D2, where D represents a symbol delay, i.e., the current output is equal to the current input minus the input two symbol periods ago.
The block diagrams of a data communications system and a data storage system presented in FIGS. 1 and 2, respectively, will be used to define the problem to be solved. In FIG. 1, data source 102 provides a data sequence {uj}, which is advantageously processed by encoder 104 to provide an encoded sequence {vk}. The data sequence is usually a binary digital stream but it could also have elements taken from an M-ary alphabet consisting of M values, where M is an integer. Likewise, the elements of the encoded sequence could be binary or M-ary. The term xe2x80x9csymbolxe2x80x9d will be used to refer to a binary or M-ary element taken from an alphabet of a set of predetermined values. For is example, a binary alphabet has two symbols, which may be 0 and 1, while an octal alphabet has eight symbols, which may be xe2x88x927, xe2x88x925, xe2x88x923, xe2x88x921, 1, 3, 5, and 7. Thus, a data sequence is made up of data symbols and an encoded sequence is made up of encoded symbols. With reference to FIGS. 1 and 2, the indices j and k may be different since the encoded sequence may have a length different from that of the data sequence. For example, if the encoder is a rate 1/2 error-correction encoder, then the encoded sequence is twice as long as the data sequence. Examples where the encoded sequence is the same length as the data sequence include: (i) the encoder is simply a one-to-one mapper such as mapping xe2x80x9c0xe2x80x9d to xe2x80x9cxe2x88x921xe2x80x9d and xe2x80x9c1xe2x80x9d to xe2x80x9c+1xe2x80x9d, as in antipodal signaling; and (ii) the encoder is a binary, rate 1/n error-correction encoder followed by a mapping of n bits to a symbol chosen from an alphabet of size 2n. With reference to FIG. 1, the encoded sequence is supplied to modulator 122, which converts the discrete-time sequence {vk} into a continuous-time modulated signal. The modulated signal is filtered, up-converted to a higher frequency, and amplified by transmitter 124 for transmission over communications medium 126. The transmitted signal is received by receiver 128, which usually performs the functions of amplification using a low-noise amplifier, down-conversion to a lower frequency, and filtering to reject out-of-band noise. The receiver output is sampled and digitized using analog-to-digital (A/D) converter 130 to provide a digitized signal, which is advantageously processed by matched filter 132. In this exemplary arrangement, matched filter 132 is a digital filter. In implementations where matched filter 132 is an analog filter, the positions of A/D converter 130 and matched filter 132 shown in FIG. 1 are interchanged. Communications channel 120 comprises modulator 122, transmitter 124, communications medium 126, receiver 128, A/D converter 130, and matched filter 132. The channel output sequence {rk} is the output of matched filter 132. Each element of the channel output sequence is represented by a digital word made up of a number of bits dependent on the implementation. The term xe2x80x9csamplexe2x80x9d will be used to refer to a quantity that is not taken from an alphabet. Thus, the number of possible values assumed by a sample is not predetermined but dependent in part on the length of the digital word representing the sample. With this convention, rk is a channel output sample and the channel output sequence {rk} is a collection of channel output samples arranged chronologically. In general, the channel generates one or more channel output samples rk in response to an encoded symbol vk presented to the channel input. To simplify the discussion, the indices of the encoded sequence {vk} and the channel output sequence {rk} are shown in FIG. 1 to be identical to signify that there is one channel output sample for each channel input symbol. The use of the same indices for these two sequences in FIG. 1 should be considered exemplary rather than restrictive. The channel output sequence is supplied to data estimator 106 to recover the data sequence. The output of data estimator 106 is an estimated data sequence {ûj}, which is composed of estimated data symbols. The estimated data sequence is supplied to data sink 108.
FIG. 2, which is a block diagram of a data storage system, shows the encoded sequence being supplied to modulator 222, which converts the discrete-time sequence {vk} into a continuous-time modulated signal. The modulated signal is supplied to data recorder 224, which writes the modulated signal onto recording medium 226, which can represent a magnetic tape or disk. Data reader 228 reads recording medium 226 to provide an analog signal, which is sampled and digitized using A/D converter 230. Recording channel 220 comprises modulator 222, data recorder 224, recording medium 226, data reader 228, and A/D converter 230.
FIGS. 1 and 2 use the same reference numerals for data source 102, encoder 104, data estimator 106, and data sink 108 to show the similarities between the data communications and data storage problems to be solved. Such a convention in notation should be considered exemplary rather than restrictive. FIG. 3 shows a block diagram that could represent either a data communications or a data storage system. Channel 300 could be communications channel 120 or recording channel 220.
The intersymbol interference found in a channel output sample is usually made up of precursor and postcursor portions. The precursor ISI is defined as the interference on the current sample from the future symbols while postcursor ISI is the interference from the past symbols. The channel output sample for the k""th symbol interval, in response to the application of the encoded sequence {vk} to the channel input, may be represented as                               r          k                =                                            ∑                              i                =                                  -                                      L                    1                                                                              -                1                                      ⁢                                          h                i                            ⁢                              v                                  k                  -                  i                                                              +                                    h              0                        ⁢                          v              k                                +                                    ∑                              i                =                1                                            L                2                                      ⁢                                          h                i                            ⁢                              v                                  k                  -                  i                                                              +                      n            k                                              (        1        )            
where hi, i=xe2x88x92L1, . . . ,0,L2 are the coefficients the channel impulse response (CIR) and nk is a noise term. In general, these quantities are complex, having real and imaginary parts. The quantity h0 is the channel gain on the desired symbol and the quantities hi, ixe2x89xa00, are the gains of the ISI components. The term xe2x80x9cISI profilexe2x80x9d will be used to mean a set of channel gain coefficients such as {hi}. The first term on the right-hand side of the above equation is the precursor ISI, which has a span of L1 symbols, the second term is the desired signal, and the third is the postcursor ISI, which has a span of L2 symbols. It can be seen from the above equation that, depending on the CIR and the encoded symbols, the ISI can result in a reduction of the signal amplitude, leading to degradation in the reliability with which data can be recovered. For example, if the CIR parameters are L1=L2=1, hxe2x88x921=h1=0.5, and h0=1, and the encoded sequence is such that vkxe2x88x921=vk+1=xe2x88x921, vk=1, then from equation (1), rk=nk, which contains no desired signal component.
The problem to be solved is to estimate the data sequence {uj} based on having observed the channel output sequence {rk}, which contains ISI. I will review the prior art on solving the problem of data recovery in the face of ISI and discuss areas where improvements may be desirable.
It is well known to those skilled in the art that the optimum estimator, in terms of providing the lowest probability of estimation error in the presence of additive white Gaussian noise (AWGN), is the maximum likelihood sequence estimator (MLSE). The Viterbi algorithm (VA) has been demonstrated to be an efficient implementation of MLSE in the article: xe2x80x9cMaximum-Likelihood Sequence Estimation of Digital Sequence in the Presence of Intersymbol Interference,xe2x80x9d by G. D. Forney, Jr., IEEE Transactions on Information Theory, vol. IT-18, pp. 363-378, May 1972. In MLSE, the channel is modeled as a linear transversal filter equivalent to a convolutional encoder operating on the data sequence. The MLSE implemented using the Viterbi algorithm, referred to here as the VA-MLSE, has ML1+L2 states, where M is the alphabet size of the symbols vk, i.e., vk can take on one of M values. Therefore, the complexity of the MLSE estimator grows exponentially with the ISI span, L1+L2. Even for a moderately small alphabet size of 4, and fairly small ISI span L1=L2=2, the number of states needed in the MLSE estimator is 44=256, which is considered a large number of states to implement for a Viterbi algorithm.
The high complexity of the VA-MLSE has an impact on the power consumption of the circuitry implementing the estimator. Keeping the power consumption to the minimum is critical in some applications, such as hand-held and mobile communications terminals. U.S. Pat. No. 5,644,603, xe2x80x9cMaximum-Likelihood Sequence Estimator with Variable Number of States,xe2x80x9d issued to A. Ushirokawa on Jul. 1, 1997, discloses a means for estimating the ISI span and selecting from a group of VA-MLSEs of different number of states to match the estimated ISI span. This approach may ease the power consumption but does not reduce the hardware/software complexity.
The use of MLSE in conjunction with forward-error-correction (FEC) coding has been suggested. For example, U.S. Pat. No. 5,673,291, xe2x80x9cSimultaneous Demodulation and Decoding of a Digitally Modulated Radio Signal using Known Symbols,xe2x80x9d issued to P. Dent on Sep. 30, 1997 discloses an apparatus for performing demodulation and decoding simultaneously using a VA-MLSE. In this approach, a data sequence to be transmitted is encoded using a block or convolutional code. Symbols known to the receiver are inserted into the encoded sequence and the composite sequence is interleaved. The known symbols are used to aid the decoding for recovery of the data sequence. A drawback of this approach is that the known symbol represent an overhead in the channel, thus reducing the bandwidth efficiency of the system.
Another example of the use MLSE in conjunction with FEC coding is U.S. Pat. No. 5,844,946, xe2x80x9cSoft-Decision Receiver and Decoder for Digital Communication,xe2x80x9d issued to T. Nagayasu on Dec. 1, 1998. In the first step, the invention of Nagayasu employs a VA-MLSE to process the received signal to estimate the transmitted symbols. In the second step, a maximum a posteriori (MAP) algorithm is used to calculate the soft-decision reliability values for the estimated symbols. In the last step, the soft-decision values are applied to a Viterbi decoder for the convolutional code. A drawback of this approach is its high complexity, particularly the complexity of the MAP algorithm.
A technique simpler than the MLSE for processing signals with ISI is linear equalization. The theory of linear equalizers is well known to those skilled in the art, see the article: xe2x80x9cAdaptive Equalization,xe2x80x9d by S. Qureshi, IEEE Communications Magazine, March 1982, pp. 9-16. One implementation of a linear equalizer employs a transversal filter, also referred to as a tapped-delay line filter, which is made up of delay elements, multipliers, and adders. The output of a transversal filter whose input is the channel output sequence {rk} may be expressed as                               q          k                =                              ∑                          i              =                              -                                  N                  1                                                                    N              2                                ⁢                                    w              i              *                        ⁢                          r                              k                -                i                                                                        (        2        )            
where wi, i=xe2x88x92N1, . . . ,0, . . . ,N2, are the tap weights, the asterisk denotes complex conjugation, and the parameters N1 and N2 are the number of precursor and postcursor equalizer taps, respectively, so that the total number of taps or multipliers is N1+N2+1. Equation (2) is called a finite convolution in light of the fact that it convolves the finite-duration impulse response of the filter, {wi}, with the filter input, {rk}, to provide the filter output qk. The tap weights are selected according to criterion such as the zero-forcing or minimum mean-square-error (MMSE) criterion. In the zero-forcing algorithm, the tap weights are selected such that the filter output qk contains as little ISI as possible. The zero-forcing algorithm leads to a filter with a transfer function, w(z), in z-transform notation, that approximates the inverse of the transfer function of the channel, h(z), i.e., w(z)≈1/h(z). In the MMSE criterion, the tap weights are set to minimize the statistical mean value of the square of the error signal vkxe2x88x92qk, where vk is the k""th transmitted symbol. When the noise power is small compared to the signal power, the MMSE criterion leads to a filter that approximates a zero-forcing filter. In general, the output of a linear equalizer will contain noise and some residual ISI. In fact, in removing ISI, a linear equalizer increases the amount of noise in the signal, a phenomenon known as noise enhancement. This phenomenon can be understood by realizing that the transfer function of a channel that exhibits ISI has smaller amplitudes at some frequencies. In fact, ISI can lead to one or more nulls in the channel transfer function. As pointed out above, the removal of ISI requires that the transfer function of the equalizer to approach the inverse of the transfer function of the channel. At frequencies where the channel transfer function has small amplitudes, the equalizer transfer function will have large gains. The large gains amplify the noise, resulting in a reduction of the signal-to-noise ratio at the output of the equalizer. Another effect of equalization is that the equalized noise spectrum is not flat and hence the noise samples are correlated. This effect is called noise colorization. The noise-enhancement and noise-colorization effects degrade the reliability with which the data sequence can be recovered. As a consequence, a linear equalizer does not provide as reliable an estimate of the data sequence as a MLSE.
An equalizer with the capability to adjust its tap weights in response to variations in the channel characteristics is called an adaptive equalizer. The theory of adaptive equalizers is well known to those skilled in the art, see the article by S. Qureshi referenced above. A commonly used technique for adaptively adjusting the tap weights is the least mean square (LMS) algorithm. In describing the LMS algorithm it proves convenient to represent the tap weights as a column vector with (N1+N2+1) elements: w=(wxe2x88x92N1, . . ,w0, . . . ,wN2)T, where the superscript T stands for the transpose operation. Let wk denote the tap weight vector at time k. A similar notation is used on the equalizer input, thus rk=(rk+N1, . . . ,rk, . . . ,rkxe2x88x92N2)T. Note that the vector rk has the elements written in the reverse time order, with the newest channel output sample listed first. With this representation, the equalizer output can be written as
qk=wkHrkxe2x80x83xe2x80x83(3)
where the superscript H represents Hermitian transposition, i.e., complex conjugation and transposition combined. Let dk be the desired equalizer output for the k""th symbol interval, then the error signal is
ek=dkxe2x88x92qk.xe2x80x83xe2x80x83(4)
In the LMS algorithm, the equalizer tap weight vector wk+1 for use in the next symbol interval to process the input signal is computed from the current tap weight vector wk according to
wk+1=wk+xcexcrke*kxe2x80x83xe2x80x83(5)
where xcexc is an adaptation time constant that controls the rate of adaptation and affects how closely the tap weights can be adjusted to the optimum values in response to variations in the channel characteristics.
As mentioned earlier, a drawback of a linear equalizer is the noise-enhancement effect. To reduce the amount of noise enhancement, a decision feedback equalizer, also well known to those skilled in the art, can be used instead of a linear equalizer. A decision feedback equalizer has a feedforward section that is identical to the transversal filter, with the channel output sequence {rk} as its input, and a feedback section with estimates of past symbols, denoted as {{circumflex over (v)}i}, as its input. The output of a decision feedback equalizer may be written as                               q          k                =                                            ∑                              i                =                                  -                                      N                    1                                                              0                        ⁢                                          w                i                *                            ⁢                              r                                  k                  -                  i                                                              +                                    ∑                              i                =                1                                            N                2                                      ⁢                                          w                i                *                            ⁢                                                v                  ^                                                  k                  -                  i                                                                                        (        6        )            
where N1+1 and N2 are the number of taps in the feedforward and feedback sections, respectively, of the equalizer. A comparison of equations (2) and (6) shows that for the decision feedback equalizer a tap weight with a subscript of 1 or higher multiplies a past symbol decision rather than a channel output sample. If the past symbol decisions are correct, then a decision feedback equalizer will have less noise enhancement than a linear equalizer. If an error occurs in the estimated symbols {{circumflex over (v)}i}, the error would propagate down the feedback section and affect the output for multiple symbols. This phenomenon is called the error-propagation effect of decision feedback equalizers and can degrade the reliability of the data recovery. This effect is particularly noticeable for systems using forward-error correction coding. Since the decoding delay is usually too big for the decoder output to be used as an input to the feedback section, the symbol decisions supplied to the equalizer must be the less-reliable decisions obtained prior to decoding.
A number of techniques have been suggested to overcome the error-propagation effects in decision feedback equalizers. U.S. Pat. No. 5,541,956, xe2x80x9cAdaptive Equalizer and Adaptive Diversity Equalizer,xe2x80x9d issued to K. Ueda on Jul. 30, 1996, discloses a system with a decision feedback adaptive equalizer, a linear equalizer, a comparing circuit, and a selecting circuit. The selecting circuit chooses the equalizer that has the better performance as determined by the comparing circuit, which compares the integrated estimation error value of the decision feedback equalizer with the integrated estimation error value of the linear equalizer. Another technique for dealing with error-propagation effects in decision feedback equalizers is disclosed in U.S. Pat. No. 5,668,833, xe2x80x9cDecision-Feedback Type Equalizer,xe2x80x9d issued to Y. Kurokami et al. on Sep. 16, 1997. The Kurokami invention provides a means for detecting an abnormal state and a selection circuit used for selecting either equalization signals or symbol decisions for supplying them as input signals to the backward equalizer, in order to reduce propagation or magnification of errors caused by noise. U.S. Pat. No. 5,742,642, xe2x80x9cSignal Processing Method and Apparatus for Reducing Equalizer Error,xe2x80x9d issued to A. Fertner on Apr. 21, 1998, presents a method for detecting incorrect symbol decisions and correcting the errors to prevent propagation of the error with possible adverse effects on subsequent equalizer decisions. U.S. Pat. No. 5,774,504, xe2x80x9cEqualization and Decoding for Digital Communication Channel,xe2x80x9d issued to S. R. Huszar et al. on Jun. 30, 1998, discloses a multiple sub-channel decision feedback equalizer/decoder which samples the received signal at an integer multiple of the symbol rate, creating multiple sub-channels. Estimates of each of the sub-channels are updated using a locally best estimate in the equalizer/decoder processing, thereby avoiding delay in updating channel estimates in a rapidly changing channel such as a digital cellular communications channels. The techniques proposed by these patents employ various arrangements to ease the error-propagation effects of decision feedback equalizers at the expense of an increase in complexity of hardware and software. Furthermore, the error-propagation effects are only reduced, not completely eliminated.
The article: xe2x80x9cDelayed Decision-Feedback Sequence Estimation,xe2x80x9d by A. Duel-Hallen and C. Heegard, IEEE Transactions on Communications, vol. 37, pp. 428-436, May 1989, proposed the use of decision feedback to reduce the number of states in MLSE. The number of states in a delayed decision feedback sequence estimator is MLxe2x88x92K, where M is the alphabet size, L is the ISI span of the channel, and K is an integer greater than one. The estimator complexity is still an exponential function of the alphabet size but is reduced by including in the estimator a number of symbols less than the ISI span. The article: xe2x80x9cComplex Noncoherent Receivers for GMSK Signals,xe2x80x9d by N. Benvenuto et al., IEEE Journal on Selected Areas in Communications, vol. 17, No. 11, pp. 1876-1885, November 1999, describes the use of a delayed decision feedback sequence estimator to demodulate a GMSK signal transmitted over a fading channel. U.S. Pat. No. 5,870,433, xe2x80x9cMethod of Processing Signals in a Viterbi Decoder According to Delayed Decision Feedback Sequence Estimation (DDFSE) Algorithm,xe2x80x9d issued to J. Huber et al. on Feb. 9, 1999, discloses a Viterbi decoder which uses a number of feedback filters to determine branch or path metrics in the trellis diagram, where this number is a function of the number of states in the trellis diagram. In the disclosed arrangement, each of the feedback filters being used is split into two parts. The first part contains the portion of the branch metrics that can be different for each path in the trellis diagram. The second part is only determined once for all paths along the path with the smallest path metrics at the end of the first part of the feedback filters. A drawback of these techniques is that the number decoder states is equal to Mn where M is the alphabet size and n is an integer smaller than the ISI span. This exponential dependence of the number of decoder states on the alphabet size makes the implementation feasible only for small alphabets or when the parameter n can be chosen to be small.
The journal articles and U.S. patents on equalization cited above consider systems without the use of error-correction coding. Equalizers, linear or decision feedback, have been used in conjunction with error-correction decoders. U.S. Pat. No. 5,872,817, xe2x80x9cJoint Viterbi Decoder and Decision Feedback Equalizer,xe2x80x9d issued to L. Wei on Feb. 16, 1999, discloses a system which employs trellis coded modulation and a bank of decision feedback equalizers, one for each state in the decoder. The arrangement is intended to provide symbol decisions to the decision feedback equalizers without excessive delay due to decoder by making use of the tentative decisions associated with each state in the decoding trellis. The equalized signal is used to update the decoder path metrics. The article: xe2x80x9cJoint Coding and Decision Feedback Equalization for Broadband Wireless Channels,xe2x80x9d by S. Ariyavisitakul and Y. Li, IEEE Journal on Selected Areas in Communications, vol. 16, No. 9, pp. 1670-1678, December 1998, describes an approach for joint convolutional coding and decision feedback equalization based on the use of both soft decisions and delayed tentative decisions. Soft decisions are obtained by passing the real and imaginary parts of the equalizer output through a hyperbolic tangent function. Tentative decisions from the Viterbi decoder are used both to cancel ISI caused by multipath with large delays and to adapt the equalizer. The article states that a tentative decoding delay approximately equal to the constraint length of the code is found to be provide near-optimum performance. U.S. Pat. No. 5,546,430, xe2x80x9cDetector for Demodulating a Received Signal and Producing an Information Data Signal with Reduced Intersymbol Interference,xe2x80x9d issued to K. Liao et al. on Aug. 13, 1996 discloses a detector for decoded trellis-coded modulation signal corrupted by ISI. The detector comprises a predictor, a feedforward filter, and a trellis coded modulation estimator with a feedback filter that is adjusted with respect to the feedforward filter to form a decision feedback equalizer. A general approach of this group of techniques is to remove the ISI using a decision feedback equalizer, aided by arrangements that help to reduce the error propagation, and then decode the ISI-free signal. Such a cascade of two operations is sub-optimum since it yields less reliable data recovery than a technique, such as MLSE, that simultaneously removes the ISI and decodes the signal.
The article: xe2x80x9cSoft-Output Equalization and TCM for Wireless Personal Communications,xe2x80x9d by Y. Chen et al., IEEE Journal on Selected Areas in Communications, vol. 16, No. 9, pp. 1679-1690, December 1998, describes the use of a maximum a posteriori probability (MAP) algorithm to realize soft-output equalization in a concatenated equalization and trellis coded modulation (TCM) decoding system. MAP algorithms compute the conditional probabilities of symbols. The computation involves a nonlinear function and requires knowledge of the noise variance. The article proposes a modified MAP algorithm that does not require knowledge of the noise variance and computes the probabilities in the logarithmic domain to avoid the need to calculate a nonlinear function. U.S. Pat. No. 5,825,832, xe2x80x9cMethod and Device for the Reception of Signals Affected by Inter-Symbol Interface,xe2x80x9d issued to V. Benedetto on Oct. 20, 1998, discloses a receiver for a trellis-code modulated signal comprising two cascaded Viterbi decoders. The first decoder is intended essentially to take into account the memory effects of the channel. The output of the first decoder, which comprises a hard decision on the transmitted symbols as well as a reliability parameter, is supplied, possibly after a de-interleaving action, to the second Viterbi decoder that carries out the actual decision. The use of the first decoder instead of an equalizer to handle ISI reduces the noise enhancement and noise correlation effects. Like the techniques discussed in the preceding paragraph, this set of techniques employs a cascade of ISI equalization and FEC decoding operations and hence yields a sub-optimum performance when compared to a technique that simultaneously removes the ISI and decodes the signal.
U.S. Pat. No. 5,031,195, xe2x80x9cFully Adaptive Modem Receiver using Whitening Matched Filtering,xe2x80x9d issued to P. R. Chevillat et al. on Jul. 9, 1991, discloses a technique for combining equalization and decoding of trellis-coded modulation using a decoder with combined ISI-and-code states. The number of states, which is the product of the number of code states and the number of ISI states, can be too large for practice. The Chevillat invention also discloses a decoder that ignores some ISI so as to reduce the complexity.
The use of an encoder that includes precoding has been employed to pre-distort the signal in order to compensate for the distortion that the channel is expected to introduce. A commonly used preceding technique is the Tomlinson-Harashima preceding algorithm described in the article: xe2x80x9cCombined Equalization and Coding Using Precoding,xe2x80x9d by G. D. Forney, Jr. and M. V. Eyuboglu, IEEE Communications Magazine, December 1991. Suppose the alphabet of the data is a set with M points: A={xc2x11,xc2x13, . . . ,(Mxe2x88x921)}. Suppose that uk is the k""th data symbol taken from the signal set A and that the channel impulse response {hi} is assumed to have only postcursor ISI and is known at the transmitter. The data symbol uk is precoded into symbol vk according to the following:                               v          k                =                              u            k                    +                      2            ⁢                          xe2x80x83                        ⁢                          Mz              k                                -                                    ∑                              j                ≥                1                                            xe2x80x83                                      ⁢                                          h                j                            ⁢                              v                                  k                  -                  j                                                                                        (        7        )            
where the value of zk is selected such that vk lies in the interval (xe2x88x92M,M]. The calculation of zk and the addition of the term 2Mzk are called a modulo-2M operation. The last term in the above equation removes the ISI caused by the previous symbols. The channel output sample is
rk=uk+2Mzk+nk.xe2x80x83xe2x80x83(8)
It can be seen that the channel output has no ISI. To recover the transmitted symbol uk, the receiver could first performs a modulo-2M operation to yield {tilde over (r)}k and then selects from the signal set A the point that is closest to {tilde over (r)}k as the estimated data symbol ûk.
The use of preceding raises the average transmit power since the maximum precoded symbol amplitude is M, which can be contrasted with the maximum uncoded data symbol amplitude of Mxe2x88x921. The increase in the average transmit power is shown in the article by Forney and Eyuboglu to be M2/(M2xe2x88x921), which can be significant if M is small. U.S. Pat. No. 5,488,633, xe2x80x9cIntersymbol Interference Channel Coding Scheme,xe2x80x9d issued to R. Laroia on Jan. 30, 1996, discloses a technique for combining precoding and trellis coding. An intersymbol interference coder uses a feedback loop to apply a dither sequence to a sequence of input signal points. The dither signal applied to each input signal point is a function of the previous signal points in the sequence. It is stated in the patent specification that the precoding loss is independent of the number of coset partitions used to generate the trellis code, thus the preceding loss is reduced compared to prior art.
U.S. Pat. No. 5,513,216, xe2x80x9cHybrid Equalizer Arrangement for Use in Data Communications Equipment,xe2x80x9d issued to S. Gadot et al. on Apr. 30, 1996 and U.S. Pat. No. 5,604,769, xe2x80x9cHybrid Equalizer Arrangement for Use in Data Communications Equipment,xe2x80x9d issued to J. Wang on Feb. 18, 1997 disclose techniques for setting the precoder coefficients based on measurements made at the receiver using a hybrid intersymbol interference decision feedback equalizer (ISI-DFE) and a noise predictive decision feedback equalizer (NP-DFE). In particular, a hybrid DFE is designed so that the I(z) coefficient values dominate over the N(z) coefficient values. In the first patent, a respective Tomlinson precoding scheme in the transmitter uses only the I(z) values. In the second patent, the precoding coefficients are set to be (1+I(z)) (1+N(z))xe2x88x921.
In certain applications, it is desirable to transmit a constant-envelope signal. Such applications include transmitters that operate the power amplifier at saturation to achieve higher power efficiency. A constant-envelope signal has the desirable property that it is not degraded by a saturating amplifier. Clearly, precoding cannot be used if a constant-envelope signal is desired. Another drawback of precoding is that the channel impulse response must be known at the transmitter.
I will now discuss prior art in ISI compensation in magnetic storage systems. The use of an equalizer followed by a Viterbi decoder has been proposed for combating ISI in magnetic storage devices. Here, the Viterbi decoder is used to perform maximum likelihood estimation of the read-back data corrupted by ISI by treating the ISI channel as an encoder. U.S. Pat. No. 5,343,335, xe2x80x9cSignal Processing System Having Intersymbol-Interference Canceling Means and Method of Same,xe2x80x9d issued to M. Hara on Aug. 30, 1994, discloses a reproduction equalizer comprising a linear equalization means, a nonlinear cancellation means for canceling the intersymbol interference included in the linearly equalized signal, a decoding means for decoding the ISI-free signal. U.S. Pat. No. 5,581,568, xe2x80x9cData Detection Apparatus,xe2x80x9d issued to M. Togami on Dec. 3, 1996, discloses an arrangement that uses an integral equalizer for low-frequency-emphasizing-type equalization to provide a larger margin in detection timing and a higher signal-to-noise ratio. The arrangement uses a Viterbi decoder to process the equalized signal. U.S. Pat. No. 5,606,464, xe2x80x9cCancellation of Precursor Intersymbol Interference in Magnetic Recording Channels,xe2x80x9d issued to 0. Agazzi et al. on Feb. 25, 1997 discloses a technique in which an adaptive filter is used to provide a replica of the precursor ISI, which is then subtracted from a delayed version of the data signal. The signal provided to the adaptive filter (to provide the precursor ISI replica) may be based on tentative decisions generated by a symbol-by-symbol detector. The equalized signal is then supplied to a Viterbi decoder. The invention does not specifically deal with postcursor ISI. It is mentioned in the specification of the patent that postcursor ISI can be compensated for using a conventional technique known as decision-feedback equalization. U.S. Pat. No. 5,889,823, xe2x80x9cMethod and Apparatus for Compensation of Linear or Nonlinear Intersymbol Interference and Noise Correlation in Magnetic Recording Channels,xe2x80x9d issued to 0. Agazzi et al. on Mar. 30, 1999, discloses an arrangement which employs a Viterbi decoder concatenated with a postprocessor. The Viterbi decoder generates N most likely paths. The postprocessor computes metrics for each of these paths. The path with the best metric is selected as the concatenated decoder output. For simplicity of implementation, the Viterbi decoder neglects some of the components of the channel impulse response that result in linear or nonlinear intersymbol interference. It may also neglect noise correlation. The postprocessor computes metrics taking into account the channel components and noise correlation neglected by the Viterbi decoder. The postprocessor can afford to carry out this more detailed analysis because it restricts its search to a small number of paths. The article: xe2x80x9cViterbi Detection of Class IV Partial Response on a Magnetic Recording Channel,xe2x80x9d by R. Wood and D. Petersen, IEEE Transactions on Communications, vol. COM-34, No. 5, pp. 454-461, May 1986, proposes a Viterbi decoder for a partial-response signaling with a discrete-time transfer function of (1xe2x88x92D2), which is referred to as a class IV partial response (PR4) signaling. In the proposed arrangement, a filtered, equalized, and sampled signal is supplied to a Viterbi decoder. U.S. Pat. No. 5,949,831, xe2x80x9cMethod and Apparatus for Data Detection for PRML Data Channels,xe2x80x9d issued to J. Coker et al. on Sep. 7, 1999, discloses an arrangement that supplies a sampled and filtered signal simultaneously to a Viterbi detector to provide a Viterbi output and to a matching delay circuit to provide a delayed signal. The Viterbi output is subtracted from the delayed signal and the resulting signal is applied to a filter to provide an output that is used correct the Viterbi output to generate the final decoder output. In these techniques, the Viterbi algorithm is used to decode the ISI. Joint ISI compensation and FEC decoding is not considered.
The article: xe2x80x9cTrellis Coding for Partial-Response Channels,xe2x80x9d by J. Wolf and G. Ungerboeck, IEEE Transactions on Communications, vol. COM-34, No. 8, pp. 765-773, August 1986, proposes the use of trellis coding to provide a coding gain over partial-response signaling with a discrete-time transfer function of (1xe2x88x92D), which is referred to as a dicode signaling. The proposed arrangement employs a binary convolutional encoder, a precoder, and at the receiver, a Viterbi decoder with twice as many states as the convolutional encoder. The extra decoder states are to accommodate the states introduced by the partial-response channel. A drawback of this arrangement is that the extra decoder states for accommodating the ISI increase the complexity of the decoder.
In summary, the prior art on intersymbol interference compensation using a maximum likelihood sequence estimator (MLSE) yields the best reliability in data recovery. The MLSE, however, is very complex. The number of estimator states required is MLxe2x88x921 where M is the alphabet size of the channel input symbols and L is the length of the ISI span of the channel. Use of delayed decision feedback sequence estimation reduces the number of estimator states to MLxe2x88x92K, where K is an integer greater than one. But the complexity is still an exponential function of the ISI span. Furthermore, the estimator now must deal with decision errors in the feedback path. Simpler ISI compensation techniques such as linear equalizers, which have a complexity linearly proportional to the ISI span, have inferior performance due to noise enhancement and noise colorization. Decision feedback equalizers improve performance over linear equalizers by reducing the amount of noise enhancement and noise colorization but suffer from error-propagation effects. Techniques to address the error-propagation lead to added complexity. Precoding, such as the Tomlinson-Harashima algorithm, introduces a loss at the transmitter since precoding increases the maximum amplitude of the transmitted symbols. In addition, precoding cannot be used if a constant-envelope signal is to be transmitted. In systems where FEC coding is used, the general prior art has been to compensate for the ISI and then FEC decode the ISI-free signal. Techniques to generate soft-decision for the FEC decoder tend to be complex.
The object of the present invention is to provide a method for intersymbol interference compensation that meets these goals: (i) a method that is less complex than maximum likelihood sequence estimation and delayed decision feedback sequence estimation; (ii) a method that performs better than the linear equalizer in terms of less noise enhancement and noise colorization; (iii) a method that is substantially free of the error-propagation effects of decision feedback equalizers; and (iv) a method that supports constant-envelope signaling as well as non-constant envelope signaling.
According to one embodiment of the present invention, the intersymbol interference compensation (ISIC) method comprises an encoding step performed by an encoder and a data estimating step performed by a data estimator. The encoder performs at least a trellis encoding of a data sequence using a trellis forward-error-correction (FEC) code such as a binary convolutional code or trellis coded modulation (TCM) code to provide a sequence of symbols for use as the input sequence to a channel. The output of the channel, referred to as the channel output sequence, comprises of samples represented as digital words. The data estimator advantageously processes the channel output sequence to provide an estimated data sequence. The data estimator comprises at least a partial equalizer, a template generator, and an ISIC decoder. The channel output sequence is supplied to the partial equalizer to provide a partially equalized sequence that is substantially free of the precursor ISI but contains at least some of the postcursor ISI of the channel output samples. The partially equalized sequence is applied to the ISIC decoder, which performs trellis decoding and ISI compensation simultaneously. The ISIC decoder implements a trellis decoding algorithm that computes branch metrics for a decoding trellis based on a set of templates {circumflex over (q)}(xe2x80xa2,xe2x80xa2). The templates are computed by taking into account the unequalized postcursor ISI and represent the statistical average values of the partially a equalized samples. The template generator supplies the template {circumflex over (q)}(x,y) in response to a pair of vectors (x,y) provided by the ISIC decoder, where x is the vector of symbols associated with the past branch or branches connected to a current branch in the decoding trellis, and y is the vector of symbols associated with the current branch. The number of states in the ISIC decoder is determined by the trellis code and is independent of the ISI span of the channel. The output of the ISIC decoder is the estimated data sequence for use by the data sink.
In one embodiment of the present invention, the equalizer tap weights are pre-computed and preloaded into the partial equalizer. The templates are either preloaded into the template generator or computed when needed by the template generator using a set of preloaded coefficients representing the ISI profile at the output of the partial equalizer. This is the preferred embodiment when the ISI profile of the channel is time-invariant and known a priori.
In another embodiment of the present invention, the equalizer tap weights are adaptive, adjusted in response to variations in the ISI profile of the channel. This is the preferred embodiment when the channel is time varying or when the channel ISI profile is not known a priori with sufficient accuracy. The invention provides for methods for partial equalizer adaptation based on known symbols called training symbols and adaptation based on estimated symbols. The desired output of the partial equalizer is the template {circumflex over (q)}(a,b), where a is a vector of past encoded symbols and b is the current encoded symbol. Subtracting the partial equalizer output from the desired output {circumflex over (q)}(a,b) yields an error signal that is used to adapt the equalizer tap weights. In yet another embodiment of the present invention, an ISI profile estimator is employed to estimate the impulse response of the channel. The estimated ISI profile is used to update the templates.
In yet another embodiment of the present invention, the channel output sequence is supplied to a double-sided partial equalizer, which leaves some of the precursor and postcursor ISI unequalized. In particular, the double-sided partial equalizer removes only the ISI not accounted for by the double-sided templates ŝ(a,b,c), where a, b, and c represent the past, current, and future encoded symbols. (The term xe2x80x9cdouble-sided templatexe2x80x9d is chosen to signify that ŝ(xe2x80xa2,xe2x80xa2,xe2x80xa2) depends on both past and future symbols. In contrast, the template {circumflex over (q)}(xe2x80xa2,xe2x80xa2) does not depend on future symbols and will be referred to as a single-sided template. The term xe2x80x9ctemplatexe2x80x9d will be used to refer to either {circumflex over (q)}(xe2x80xa2,xe2x80xa2) or ŝ(xe2x80xa2,xe2x80xa2,xe2x80xa2) when its meaning is clear.) Thus, the desired output of the double-sided partial equalizer is ŝ(a,b,c). The output of the double-sided partial equalizer is supplied to a decision-directed-ISIC (DD-ISIC) decoder. In this embodiment of the present invention, the output of the ISIC decoder is not supplied to the data sink but is supplied instead to the DD-ISIC decoder for use as interim data decisions. The DD-ISIC decoder computes the branch metrics using the templates ŝ(x,y,z) with z representing the vector of symbols associated with the future branch or branches in the decoding trellis as determined by the interim data decisions. The output of the DD-ISIC decoder is the estimated data sequence for use by the data sink.
In yet another embodiment of the present invention, concatenated coding is employed wherein the data sequence is applied to a cascade of an outer FEC encoder, an interleaver and at least a trellis encoder to provide an encoded sequence for use as the channel input. At the data estimator, the channel output samples are advantageously processed by a partial equalizer and an ISIC decoder to provide a sequence that is further advantageously processed by a cascade of a deinterleaver and an outer FEC decoder to provide an estimated data sequence for use by the data sink.
In yet another embodiment of the data estimator for use with concatenated coding, the ISIC decoder output is supplied to a cascade of a first deinterleaver, a first outer FEC decoder, an outer FEC encoder, and an interleaver to provide an outer-FEC-decoded sequence for use by a DD-ISIC decoder as interim data decisions. The DD-ISIC decoder output is supplied to a cascade of a second deinterleaver and a second outer FEC decoder to provide an estimated data sequence for the data sink.
In yet another embodiment of the present invention, an error-detection code is employed to detect errors in the outer-FEC-decoded sequence. A selector is used to select the interim data decisions for use by the DD-ISIC decoder. If errors are detected in the outer-FEC-decoded sequence, the interim data decisions are set to be the output of the ISIC decoder; otherwise, they are set to be the outer-FEC-decoded sequence.